package recursion

// 给你一个可移动范围n
// 当到达1时，只能走向2
// 当到达n时，只能走向n-1
// 你的起始位置在p
// 目标位置是 q
// 只能走k步
// 返回最终可以走到q的方法数

func RobotWalk(n, p, q, k int) int {
	if n < 2 || p > n || p < 1 || q > n || q < 1 || k < 1  {
		return 0
	}
	return RobotWalkProcess(n, p, q, k)
}

func RobotWalkProcess(n, cur, dest, k int) int {
	if k == 0 {
		if cur == dest {
			return 1
		} else {
			return 0
		}
	}
	if cur == 1 {
		return RobotWalkProcess(n, 2, dest, k-1)
	}
	if cur == n {
		return RobotWalkProcess(n, n-1, dest, k-1)
	}
	var ans int
	ans += RobotWalkProcess(n, cur+1, dest, k-1)
	ans += RobotWalkProcess(n, cur-1, dest, k-1)
	return ans
}


func RobotWalkDp(n, p, q, k int) int {
	if n < 2 || p > n || p < 1 || q > n || q < 1 || k < 1  {
		return 0
	}
	return RobotWalkDpProcess(n, p, q, k)
}

func RobotWalkDpProcess(n, cur, dest, k int) int {
	dp := make([][]int, k+1)
	for i:=0; i<= k; i++ {
		dp[i] = make([]int, n+1)
	}
	// 初始化
	for i:=0; i<=n; i++{
		if i==dest {
			dp[0][i] = 1
		}
	}

	for curK:=1; curK<=k; curK++ {
		for curC:=1; curC<=n; curC++ {
			if curC == 1 {
				dp[curK][curC] = dp[curK-1][2]
			} else if curC == n {
				dp[curK][curC] = dp[curK-1][n-1]
			} else {
				dp[curK][curC] = dp[curK-1][curC-1] + dp[curK-1][curC+1]
			}
		}
	}
	return dp[k][cur]
}